package com.shigi.knapsack.solvers;

import com.shigi.knapsack.KnapsackInstance;
import com.shigi.knapsack.KnapsackItem;
import com.shigi.knapsack.KnapsackSolution;
import com.shigi.knapsack.KnapsackSolver;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by Miroslav Šiagi on 04/10/14.
 */
public class BasicHeuristic implements KnapsackSolver {

    private KnapsackSolution knapsackSolution;
    private KnapsackInstance knapsackInstance;
    private KnapsackItem[] knapsackItems;

    public KnapsackSolution solve(KnapsackInstance knapsackInstance) {
        this.knapsackInstance = knapsackInstance;
        this.knapsackSolution = new KnapsackSolution(knapsackInstance.getId());
        this.knapsackItems = knapsackInstance.getKnapsackItems();
        sortItems();
        createSolution();
        return knapsackSolution;
    }

    private void createSolution() {
        int totalWeight = 0;
        int maxWeight = this.knapsackInstance.getTotalWeight();
        int totalValue = 0;

        int itemIterator = 0;
        int numberOfItems = this.knapsackItems.length;
        while(itemIterator < numberOfItems) {
            int itemsWeight = this.knapsackItems[itemIterator].getWeight();
            if(totalWeight + itemsWeight <= maxWeight) {
                totalValue += this.knapsackItems[itemIterator].getValue();
                totalWeight += itemsWeight;
                this.knapsackSolution.setUsedItems((int) (this.knapsackSolution.getUsedItems() + Math.pow(2, (double)numberOfItems - 1 - this.knapsackItems[itemIterator].getId())));
            } else {
                break;
            }
            itemIterator++;
        }

        this.knapsackSolution.setNumberOfItems(numberOfItems);
        this.knapsackSolution.setTotalValue(totalValue);
    }

    private void sortItems() {
        Arrays.sort(this.knapsackItems, new Comparator<KnapsackItem>() {
            @Override
            public int compare(KnapsackItem o1, KnapsackItem o2) {
                double ratioOfFirstItem = getItemsRatio(o1);
                double ratioOfSecondItem = getItemsRatio(o2);
                if (ratioOfFirstItem < ratioOfSecondItem) {
                    return 1;
                } else if (ratioOfFirstItem == ratioOfSecondItem) {
                    int o1Value = o1.getValue();
                    int o2Value = o2.getValue();
                    if (o1Value > o2Value) {
                        return 1;
                    } else if (o1Value == o2Value) {
                        return 0;
                    } else {
                        return 0;
                    }
                } else {
                    return -1;
                }
            }
        });
    }

    private double getItemsRatio(KnapsackItem knapsackItem) {
        return (double) knapsackItem.getValue() / (double) knapsackItem.getWeight();
    }

}
